package com.andnnl.shudu;

import java.util.LinkedList;

/**
 * 迷宫
 */
public class GreedyMaze {
    private static int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
            {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
            {1, 0, 1, 0, 1, 0, 1, 1, 0, 1},
            {1, 0, 1, 0, 0, 0, 1, 1, 0, 1},
            {1, 1, 1, 0, 1, 1, 0, 0, 0, 1},
            {1, 0, 1, 1, 0, 1, 0, 1, 1, 1},
            {1, 0, 1, 0, 0, 0, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 1, 1, 1, 0, 1},
            {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
            {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    //    private static int[][] maze = {
//            {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
//            {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
//            {1, 0, 1, 0, 1, 1, 1, 1, 0, 1},
//            {1, 0, 1, 0, 0, 0, 0, 1, 0, 1},
//            {1, 1, 1, 0, 1, 1, 0, 1, 0, 1},
//            {1, 0, 1, 1, 1, 1, 0, 1, 1, 1},
//            {1, 0, 1, 0, 0, 0, 0, 1, 0, 1},
//            {1, 0, 1, 0, 1, 1, 1, 1, 0, 1},
//            {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
//            {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
//    };
    //上右下左
    private static int[] dx = {0, 1, 0, -1};
    private static int[] dy = {-1, 0, 1, 0};
    private static int[][] path = new int[10][10];
    private static int endX = 8;
    private static int endY = 8;

    public static void main(String[] args) {
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(new Node(1, 1));
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.x == endX && cur.y == endY) {
                System.out.println("到达终点！");
                printSimple(maze);
                printSimple(path);
                removeOther();
                break;
            }
            for (int i = 0; i < 4; i++) {
                int newX = cur.x + dx[i];
                int newY = cur.y + dy[i];
//                System.out.println(""+newX+" "+newY);
                if (newX >= 0 && newX < 10 && newY >= 0 && newY < 10 && maze[newX][newY] == 0 && path[newX][newY] == 0) {
                    queue.offer(new Node(newX, newY));
                    path[newX][newY] = path[cur.x][cur.y] + 1;
                }
            }
        }
    }


    private static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static void printSimple(int[][] a) {
        System.out.println("case");
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a.length; j++) {
                System.out.print(a[i][j] + "\t");
                if (j == a.length - 1) System.out.println("");
            }
        System.out.println("--------------------------");
    }

    /**
     * 减掉其他
     */
    private static void removeOther() {
        int[][] removePath = new int[10][10];
        int v = path[endX][endY];
        Node cur = new Node(endX, endY);
        removePath[endX][endY] = v;
        while (v > 0) {


            for (int i = 0; i < 4; i++) {
                int newX = cur.x + dx[i];
                int newY = cur.y + dy[i];
//                System.out.println(""+newX+" "+newY);
                if (newX >= 0 && newX < 10 && newY >= 0 && newY < 10 && path[newX][newY] == v - 1) {
                    cur = new Node(newX, newY);
                    removePath[newX][newY] = v - 1;
                    v--;
                    break;
//                    path[newX][newY] = path[cur.x][cur.y] + 1;
                }
            }
        }
        //            if (cur.x == 1 && cur.y == 1) {
        System.out.println("最优路径！");
        printSimple(removePath);
//                printSimple(path);
//                removeOther();
    }
}
